This specification relates to database query languages.
In computer programming languages generally, a type is a property of a programming language construct. Types restrict the operations that are permitted between constructs in the language. The type rules that define permissible operations between constructs of different types are enforced by a compiler, interpreter, or evaluation engine of the programming language. For example, the type rules in Python do not allow a variable having an integer type to be called as a function. Therefore, an interpreter for Python will raise a type error if the source code attempts this operation.
Some programming languages have algebraic data types. An algebraic data type is a type that is defined using algebraic operations on other subtypes. Algebraic data types commonly have two forms: (1) sum types defined by the union of two or more subtypes, and (2) product types that are defined by an ordered sequence of two or more subtypes.
The semantics of a sum type that uses a first subtype and a second subtype means that an instance of the sum type is considered to be either the first subtype or the second subtype, but not both. The semantics of a product type that uses a first subtype and a second subtype means that an instance of product type has instances of both the first subtype and the second subtype.
As used in this description, a database query language is a query language for a relational database that operates only on atomic values and does not allow operations on structured values, such as pairs, lists, or other structured values. Datalog is an example of a database query language that operates only on atomic values. This allows Datalog to maintain clean semantics, but makes some programming tasks cumbersome or impossible.
As used in this description, a “relation” is a set of tuples (t1, . . . , tn), each tuple having n≥1 data elements ti. Each element ti is a corresponding value, which may represent a value of a corresponding attribute. The attribute will generally have an attribute name. The correspondence between attribute and value is determined by the position of the value in the tuple, i.e., each attribute has a corresponding position. Relations are commonly thought of as, represented as, and referred to as tables in which each row is a tuple and each column is an attribute.
As used in this description, a “programming language construct” is a syntactically allowable part of a programming language. Each programming language construct has particular semantics, which defines the meaning of the programming language construct and which specifies processes that a computer should follow to compute a result for the programming language construct. A programming language construct is a built-in feature of a programming language, to be distinguished from a function, which can be user-defined.
As used in this description, an “expression” is a portion of a computer program having one or more programming language constructs.
As used in this description, an “evaluation engine” is a computer program that, when executed, evaluates expressions of a particular programming language.
As used in this description, a “predicate” of a logic programming language is an expression that when evaluated by an evaluation engine, causes the evaluation engine to generate tuples that belong to an associated relation for the predicate. When a tuple is provided as an argument to a predicate, the expression evaluates to true if the value occurs in the associated relation and false otherwise.
As used in this description, a “recursive predicate” is a predicate that references its own definition.